from collections import defaultdict
from sys import stdin
input = stdin.buffer.readline
def func():
if m % 2 == 0:
print(0)
else:
odd = list(x for x in range(1, n+1) if len(friends[x]) % 2 != 0)
even = list(x for x in range(1, n+1) if len(friends[x]) % 2 == 0)
first = 10**9
second = 10**9
if even:
for f in even:
for e in friends[f]:
first = min(first, a[f-1] + a[e-1])
if second:
for f in odd:
second = min(second, a[f-1])
print(min(first, second))
for _ in range(int(input())):
n, m = map(int, input().split())
a = list(map(int, input().split()))
friends = defaultdict(list)
for __ in range(m):
x, y = map(int, input().split())
friends[x].append(y)
friends[y].append(x)
func()
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define MAXN 100010
int x[MAXN], y[MAXN], a[MAXN], degree[MAXN];
int n, m;
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
degree[i] = 0;
cin >> a[i];
}
for (int i = 1; i <= m; i++)
{
cin >> x[i] >> y[i];
degree[x[i]]++;
degree[y[i]]++;
}
int ans = INT_MAX;
if (m % 2 == 0)
ans = 0;
for (int i = 1; i <= n; i++)
if (degree[i] % 2 == 1)
ans = min(ans, a[i]);
for (int i = 1; i <= m; i++)
if (degree[x[i]] % 2 == 0 && degree[y[i]] % 2 == 0)
ans = min(ans, a[x[i]] + a[y[i]]);
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
1365. How Many Numbers Are Smaller Than the Current Number | 771. Jewels and Stones |
1512. Number of Good Pairs | 672. Richest Customer Wealth |
1470. Shuffle the Array | 1431. Kids With the Greatest Number of Candies |
1480. Running Sum of 1d Array | 682. Baseball Game |
496. Next Greater Element I | 232. Implement Queue using Stacks |
844. Backspace String Compare | 20. Valid Parentheses |
746. Min Cost Climbing Stairs | 392. Is Subsequence |
70. Climbing Stairs | 53. Maximum Subarray |
1527A. And Then There Were K | 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers |
318. Maximum Product of Word Lengths | 448. Find All Numbers Disappeared in an Array |
1155. Number of Dice Rolls With Target Sum | 415. Add Strings |
22. Generate Parentheses | 13. Roman to Integer |
2. Add Two Numbers | 515. Find Largest Value in Each Tree Row |
345. Reverse Vowels of a String | 628. Maximum Product of Three Numbers |
1526A - Mean Inequality | 1526B - I Hate 1111 |